import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findSubstring("barfoothefoobar", new String[]{"foo", "bar"}));
        System.out.println(s.findSubstring("wordgoodgoodgoodbestword", new String[]{"word","good","best","word"}));
        System.out.println(s.findSubstring("barbarfoobarthefoobarman", new String[]{"bar","foo","the"}));
        System.out.println(s.findSubstring("aaab", new String[]{"a", "a"}));
    }
}


//官方解法：滑动窗口
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int wordLength = words[0].length();

        List<Integer> ans = new ArrayList<>();
        for(int offset = 0; offset < wordLength; offset++){
            if(s.length() < wordLength * words.length + offset){
                break;
            }

            //初始化
            Map<String, Integer> differ = new HashMap<>();
            for(String word: words){
                differ.put(word, differ.getOrDefault(word, 0) - 1);
            }
            for(int i = 0; i < words.length; i++){
                String word = s.substring(offset + i * wordLength, offset + (i + 1) * wordLength);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
                if(differ.get(word) == 0){
                    differ.remove(word);
                }
            }
            if(differ.size() == 0){
                ans.add(offset);
            }

            //窗口向右滑动
            for(int i = offset + wordLength; i + wordLength * words.length <= s.length(); i += wordLength){
                String head = s.substring(i + wordLength * (words.length - 1), i + wordLength * words.length);
                differ.put(head, differ.getOrDefault(head, 0) + 1);
                if(differ.get(head) == 0){
                    differ.remove(head);
                }
                String left = s.substring(i - wordLength, i);
                differ.put(left, differ.getOrDefault(left, 0) - 1);
                if(differ.get(left) == 0){
                    differ.remove(left);
                }
                if(differ.size() == 0){
                    ans.add(i);
                }
            }
        }
        return ans;
    }
}


//自己解法
class Solution1 {
    public List<Integer> findSubstring(String s, String[] words) {
        int wordLength = words[0].length();
        int wordsLength = wordLength * words.length;

        List<Integer> ans = new ArrayList<>();
        for(int offset = 0; offset < wordLength; offset++){
            for(int i = 0; i + offset < s.length() - wordsLength + 1;){
                int start = i + offset;
                int count = maxMatch(s, start, words);
                if(count == words.length) {
                    ans.add(start);
                    i += wordLength;
                    continue;
                }
                if(count == -1){
                    i += wordLength;
                }
                else{
                    i += wordLength * (count + 1);
                }
            }
        }
        return ans;
    }

    /**
     * 返回words在s中的最长匹配单词个数，s以start开始
     * @param s
     * @param start
     * @param words
     * @return 如果全部匹配或部分匹配且下一个单词不存在，则返回words在s中的最长匹配单词个数；
     *         如果部分匹配且下一个单词重复，则返回-1（从下一个步长处继续，便于主调函数处理）
     */
    private int maxMatch(String s, int start, String[] words) {
        int wordLength = words[0].length();
        Map<String, Integer> map = new HashMap<>();  //每个单词的剩余个数
        for(String word: words){
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        int count = 0;
        for(int i = 0; i < words.length; i++){
            String prefix = s.substring(start + i * wordLength, start + i * wordLength + wordLength);
            Integer value = map.get(prefix);
            //单词不存在
            if(value == null){
                return i;
            }
            //单词匹配
            if(value > 0){
                map.replace(prefix, value - 1);
            }
            //单词重复
            else{
                return -1;
            }
        }
        return words.length;
    }

}